package LearnDataStructure.d_图结构.例题;

import java.util.*;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-16 18:44
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.d_图结构.例题
 */
/*
有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升
开始的状态是 [9,0,0,0]，也就是说：第一个瓶子满着，其它的都空着。
允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。
这样的一次倒酒动作称为1次操作。

假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？

本题就是要求你编程实现最小操作次数的计算。
图的问题，更多的情况，节点不是很明显，多是一种“状态”
瓶子倒来倒去...状态肯定是有限的

输入：最终状态（空格分隔）
输出：最小操作次数（如无法实现，则输出-1）


输入：
9 0 0 0
应该输出：
0

输入：
6 0 0 3
应该输出：
-1

输入：
7 2 0 0
应该输出：
2
 */
public class c_分酒byBFS {
    public static void main(String[] args) {
        c_分酒byBFS test = new c_分酒byBFS();
        test.useBFS();
    }

    public void useBFS() {
        Scanner scanner = new Scanner(System.in);
        String target = "";
        for (int i = 0; i < 4; i++) {
            if (i == 3) {
                target += scanner.nextInt();
            } else {
                target += scanner.nextInt() + ",";
            }
        }
        BFSNode targetNode = new BFSNode(target);
        BFSNode beginNode = new BFSNode("9,0,0,0", 0);
        int[] capacity = {9, 7, 4, 2};
        Queue<BFSNode> queue = new LinkedList<BFSNode>();
        HashSet<BFSNode> visitedStates = new HashSet<BFSNode>();

        queue.add(beginNode);
        int result = operateBFS(queue, targetNode, capacity, visitedStates);
        System.out.println(result);
    }

    /**
     * BFS+回溯
     * 使用回溯的原因是，确定currentOut需要循环，在确定currentOut后还要确定currentIn也要循环
     * 这使用穷举
     * 当currentOut变动后，为了维持state是一开始的状态，所以要回溯
     * @param queue
     * @param target
     * @param capacity
     * @param visitedStates
     * @return
     */
    public int operateBFS(Queue<BFSNode> queue, BFSNode target, int[] capacity, Set<BFSNode> visitedStates) {
        while (!queue.isEmpty()) {
            BFSNode node = queue.poll();
            if (node.equals(target)) {//广度优先遍历出口
                return node.depth;//返回有法，倒node.depth次数就能成
            }
            int[] state = node.getState();//先把每个瓶子里面的量得到
            /*
            尝试把当前状态的所有可能的后继状态(只操作一次倒酒操作产生的状态)
            罗列出来，并逐一比对是否可能存在
            因为我们不知道哪些瓶子有酒哪些没有
            所以我们只能穷举
             */
            for (int currentOut = 0; currentOut < state.length; currentOut++) {//穷举，挨个判断每个瓶子往外倒的情况
                if (state[currentOut] > 0) {//当前瓶子currentOut有酒
                    for (int currentIn = 0; currentIn < state.length; currentIn++) {//穷举，挨个判断每个瓶子接受的情况
                        if (currentIn == currentOut) {//瓶子重叠情况，手动去重
                            continue;
                        }
                        int currentInNowCapacity = capacity[currentIn] - state[currentIn];
                        //能倒，且倒空，且不撒；判断currentIn能不能装下currentOut中的所有酒
                        if (currentInNowCapacity >= state[currentOut]) {//能，则尝试完全倒入
                            int temp = state[currentOut];
                            state[currentOut] = 0;
                            state[currentIn] += temp;
                            addState(queue,new BFSNode(intArrToString(state),node.depth+1),visitedStates);//BFS
                            //回溯
                            state[currentOut] = temp;
                            state[currentIn] -= state[currentOut];
                        }
                        //能倒，且倒不空，且会倒撒
                        if (currentInNowCapacity > 0 && currentInNowCapacity < state[currentOut]) {///稍微能，则尝试倒入
                            int temp = state[currentOut];
                            state[currentOut] -= currentInNowCapacity;
                            state[currentIn] += currentInNowCapacity;
                            addState(queue,new BFSNode(intArrToString(state),node.depth+1),visitedStates);//BFS
                            //回溯
                            state[currentOut] = temp;
                            state[currentIn] -= currentInNowCapacity;
                        }
                    }
                }
            }
        }
        //跳出循环，代表穷举了所有状态，也没有符合target的状态；那么就代表无法倒出来target
        return -1;//返回无法
    }

    /**
     * 加入状态到队列
     * 同时有判断是否为重复状态的功能
     * @param queue
     * @param node
     * @param visitedStates
     */
    public void addState(Queue<BFSNode> queue, BFSNode node, Set<BFSNode> visitedStates) {
        if (!visitedStates.contains(node)) {//已确认状态中，确实没有目前的状态
            queue.add(node);
            visitedStates.add(node);
        }
    }

    /**
     * 把整型数组转成带“，”的字符串
     * @param state
     * @return
     */
    public String intArrToString(int[] state) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < state.length; i++) {
            builder.append(state[i]).append(",");
        }
        return builder.deleteCharAt(state.length * 2 - 1).toString();
    }

    static class BFSNode {
        public String value = null;
        public int depth = 0;

        public BFSNode(String value) {
            this.value = value;
        }

        public BFSNode(String value, int depth) {
            this.value = value;
            this.depth = depth;
        }

        /**
         * 把状态字符串转成四个杯子的存量，方便运算
         *
         * @return
         */
        public int[] getState() {
            String[] arr = value.split(",");
            int[] state = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                state[i] = Integer.parseInt(arr[i]);
            }
            return state;
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) {
                return true;
            }
            if (other == null || getClass() != other.getClass()) {
                return false;
            }

            BFSNode bfsNode = (BFSNode) other;

            return value.equals(bfsNode.value);
        }

        @Override
        public int hashCode() {
            return value.hashCode();
        }
    }
}
